package com.yiguang.algorithm.dp;

import java.time.LocalDateTime;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

import com.alibaba.fastjson.JSON;

/*
 * 斐波那契数列
 * 由来认识递归、记忆化搜索（回溯）和动态规划
 * 记忆化搜索和动态规划：https://www.jianshu.com/p/763302ad5c01
 */
public class FibonacciSeries {
	
	static long[] arr;
	
	public static void main(String[] args) {
		Long time1 = System.currentTimeMillis();
		System.out.println(memorySearch(100));
		Long time2 = System.currentTimeMillis();
		System.out.println(time2-time1);
		System.out.println(dp(100));
		Long time3 = System.currentTimeMillis();
		System.out.println(time3-time2);
		
		//总结：普通递归函数性能很差，动态规划性能最好，记忆化搜索次之，
		//因为记忆化搜索在递归调用中花费更多时间
	}
	
	/**
	 * 递归函数：存在大量重复运算
	 */
	public static Long ordinary(int n) {
		if(n==1||n==2) {
			return 1L;
		}
		Long result = ordinary(n-1) + ordinary(n-2);
		return result;
	}
	
	/**
	 * 动态规划之记忆化搜索
	 * 浪费太多资源做重复的事情，很自然就会想到能不能加个缓存，将结果存储在缓存中，下次求该值，先去缓存中寻找，找到直接返回，找不到再去计算，这种思想就是记忆化搜索
	 * 算法复杂度O(n)，自顶向下即记忆化递归
	 * 斐波那契数的边界条件是 F(0)=0 和 F(1)=1。当 n>1 时，每一项的和都等于前两项的和，因此有如下递推关系：
	 * F(n)=F(n-1)+F(n-2)
	 * 由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0)和 F(1)。
	 */
	public static Long memorySearch(int n) {
		if(n<=2) {
			return 1L;
		}
		if(Objects.isNull(arr)) {
			arr = new long[n];
			arr[0] = 1L;
			arr[1] = 1L;
		}
		
		if(arr[n-1] == 0L) {
			arr[n-1] = memorySearch(n-1)+memorySearch(n-2);
		}
		return arr[n-1];
	}
	
	/**
	 * 动态规划之递推
	 * 动态规划：将原问题拆解成若干个子问题,同时保存子问题的答案,使得每个子问题只求解一次,
	 * 时间复杂度O(n)，自底向上就是递推
	 * 状态转移方程：
	 * 用 dp[i] 表示数列的第n项，那么就有如下的状态转移方程：
	 * dp[i]=dp[i-1]+dp[i-2]
	 */
	public static Long dp(int n) {
		if(n<=2) {
			return 1L;
		}
		long[] arr = new long[n];
		arr[0] = 1L;
		arr[1] = 1L;
		
		for(int i=2; i<n; i++) {
			arr[i] = arr[i-1] + arr[i-2];
		}
		
		return arr[n-1];
	}
	
	
}
